/*
提交链接：https://leetcode.cn/problems/longest-common-subsequence/description/
1143.最长公共子序列
刘思琪 2024/9/7
*/

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int l1=text1.size(),l2=text2.size();
        int dp[1005][1005];     //二维数组前一项表示text1前i项与text2前j项的公共子序列长度
        for(int i=1;i<=l1;i++){        //从第1项算起（因为下面是i-1）
            char a=text1.at(i-1);  //找text1第i-1项元素
            for(int j=1;j<=l2;j++){
                char b=text2.at(j-1);  //找text2第j-1项元素
                if(a==b)         //相等说明在原有公共元素上长度＋1（因为长度是从0开始算起）
                dp[i][j]=dp[i-1][j-1]+1;
                else           //不等说明此时的dp[i][j]应该为dp[i-1][j]与dp[i][j-1]中的较大项
                dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            }
        }
        return dp[l1][l2];       //输出结果为最后一项
    }
};